Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness

摘要

There has been significant recent interest in game-theoretic approaches tosecurity, with much of the recent research focused on utilizing theleader-follower Stackelberg game model. Among the major applications are theARMOR program deployed at LAX Airport and the IRIS program in use by the USFederal Air Marshals (FAMS). The foundational assumption for using Stackelberggames is that security forces (leaders), acting first, commit to a randomizedstrategy; while their adversaries (followers) choose their best response aftersurveillance of this randomized strategy. Yet, in many situations, a leader mayface uncertainty about the follower's surveillance capability. Previous workfails to address how a leader should compute her strategy given suchuncertainty. We provide five contributions in the context of a general class ofsecurity games. First, we show that the Nash equilibria in security games areinterchangeable, thus alleviating the equilibrium selection problem. Second,under a natural restriction on security games, any Stackelberg strategy is alsoa Nash equilibrium strategy; and furthermore, the solution is unique in a classof security games of which ARMOR is a key exemplar. Third, when faced with afollower that can attack multiple targets, many of these properties no longerhold. Fourth, we show experimentally that in most (but not all) games where therestriction does not hold, the Stackelberg strategy is still a Nash equilibriumstrategy, but this is no longer true when the attacker can attack multipletargets. Finally, as a possible direction for future research, we propose anextensive-form game model that makes the defender's uncertainty about theattacker's ability to observe explicit.